package offer;

import java.util.Stack;

public class offerII_0028 {
    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    };

    public Node flatten(Node head) {
        Stack<Node> stack=new Stack<>();
        Node node=head;
        if(node==null) return node;
        while(true){
            if(stack.isEmpty()&&node.next==null&&node.child==null) break;
            if(node.child!=null){
                if(node.next!=null) stack.add(node.next);
                node.next=node.child;
                node.next.prev=node;
                node.child=null;
                node=node.next;

            }
            else if(node.next!=null){
                node=node.next;
            }
            else {
                node.next=stack.pop();
                node.next.prev=node;
                node=node.next;
            }

        }
        return head;
    }
}
